Thorsten Froehlich <tho### [at] trfde> wrote:
: The return is missing...

  The standard says that the return is optional (don't ask me why).

: Total:               O(n * log(n) + n * log(n))

  This is equal to O(n * log(n))

: I can get:

: Total:               O(2 * n + n * log(n))

  This is also equal to O(n * log(n))

  So in terms of O both ways are equally fast.

: How?  That is simple:  I read in the words. Then sort them and then just
: count when retrieving.

  But it uses more memory (specially if there are many repetitions).

: Of course I can do this using the STL (see below)!  But your example shows
: something dangerous you forgot:  the STL can trick you into thinking you
: have found a good algorithm, but in fact yours is nearly log(n) times slower
: than mine for most cases (for log(n) > 2)!

  The O-notation doesn't know the term "log(n) times slower" if the speed
is already at least O(log(n)).
  My version and your version have both the same O value and there's a good
reason for this in this case: Your version can be a lot slower when the
input is very big and there's a lot of repetition (imagine that the input
is "word1 word2 word1 word2..." millions of times). The speed is still
O(n*log(n)) in relation with the size of the input, but the speed factor can
vary a lot.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message